#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

#define vertex_max 8
#define edge_max   10

unsigned char visited[vertex_max + 1];

struct link 
{
  int data;
  struct link * next;
};

struct graph
{
  struct link vertex[vertex_max + 1];
};

void adjacency_link(struct graph * graph)
{
  struct link * src;
  int i, j, k;

  for (k = 1; k <= vertex_max; k++) {
    graph->vertex[k].data = k;
    graph->vertex[k].next = NULL;
  }

  for (k = 1; k <= edge_max; k++) {
    scanf("%d %d", &i, &j);

    src = (struct link *) malloc (sizeof(struct link));
    src->data = j;
    src->next = graph->vertex[i].next;
    graph->vertex[i].next = src;

    src = (struct link *) malloc (sizeof(struct link));
    src->data = i;
    src->next = graph->vertex[j].next;
    graph->vertex[j].next = src;
  }
}

void deep_first_search(struct graph * graph, int i)
{
  struct link * src;

  printf(" %d ", graph->vertex[i].data);
  visited[i] = true;

  src = graph->vertex[i].next;
  while ( src != NULL) {
    if (!visited[src->data])
      deep_first_search(graph, src->data);
    src = src->next;
  }
}

void display(struct graph * graph)
{
  int i;
  struct link * src;

  for (i = 1; i <= vertex_max; i++) {
    src = graph->vertex[i].next;
    printf("vertex=%d: ", i);
    while (src != NULL) {
      printf(" %d ", src->data);
      src = src->next;
    }
    printf("\n");
  }
}

void main()
{
  struct graph graph;
  int i;

  adjacency_link( &graph );
  display( &graph );
  
  for (i = 1; i <= vertex_max; i++)
    visited[i] = false;

  deep_first_search( &graph, 1);
  printf("\n");
}

/*
 对非连通图
 for (i = 1; i <= vertex_max; i++)
    if (!visited[i])
       deep_first_search(i)x


 */
